1. Field of the Invention
The present invention relates to a secret sharing device, method, and program using a (k, n) threshold scheme, for example, a secret sharing device, method, and program capable of realizing the (k, n) threshold scheme at high speed without using polynomial interpolation.
2. Description of the Related Art
Generally, in case secret information such as cryptographic key is lost, a measure of previously making a copy of the secret information is taken. However, making a copy of the secret information causes such a problem that increases a risk of theft. As the measure against this problem, in 1979, Shamir proposed a secret sharing method called a (k, n) threshold scheme (see, for example, A. Shamir; “How to Share a secret”, Communications of the ACM, 22, 11, pp. 612-613[1979]).
In the (k, n) threshold scheme, when the secret information is divided into n items of shared information, the original secret information can be recovered from k out of the n items of shared information but cannot be recovered at all from the k−1 items of shared information. Namely, the (k, n) threshold scheme has a secret information recovery characteristic with a threshold of k as a boundary (where 2≦k≦n).
According to the (k, n) threshold scheme, even when k−1 or less items of shared information are revealed, the original secret information is still safe and even when n−k or less items of shared information are lost, the original secret information can be recovered.
The Shamir (k, n) threshold scheme performs the processing of secret information sharing and recovery through polynomial interpolation that requires a lot of calculations, which is disadvantageous because it requires a high speed computer in order to share the secret information of large amount.
On the other hand, in order to resolve the above problem, there are known a method by Fujii and a method by Kurihara, as the (k, n) threshold scheme capable of reducing the calculation amount greatly (see, for example, Yoshihiro Fujii, Minako Tada, Norikazu Hosaka, Koya Tochikubo, and Takehisa Kato: “A Fast (2,n)-Threshold Scheme and Its Application”, SCC2005 collection of preliminary papers, (2005), and Jun Kurihara, Shinsaku Kiyomoto, Kazuhide Fukushima, and Toshiaki Tanaka: “A (3,n)-Threshold Secret Sharing Scheme using XOR Operations”, SCIS2007 collection of preliminary papers, (2007)). The Fujii method and the Kurihara method can perform the secret information sharing and recovering processing at high speed because they use only the exclusive OR operation.
The Fujii method and the Kurihara method, however, have a disadvantage that the threshold k is restricted to 2 or 3.
As set forth hereinabove, the Shamir (k, n) threshold scheme has such a disadvantage that it requires a high speed computer because of using the polynomial interpolation. On the other hand, the Fujii method and the Kurihara method have such a disadvantage that the threshold k is restricted to 2 or 3.